package com.hy;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:547. 省份数量
 * <p>
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，
 * 那么城市 a 与城市 c 间接相连。
 *
 * 省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 *
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
 * 而 isConnected[i][j] = 0 表示二者不直接相连。
 *
 * 返回矩阵中 省份 的数量。
 * User:Mr.Du
 * Date:2024/4/17
 * Time:15:38
 */
public class FindCircleNum {

    public int findCircleNum(int[][] isConnected) {
        int m = isConnected.length, n = isConnected[0].length;
        QuickUnionUF uf = new QuickUnionUF(m);
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(isConnected[i][j] == 1) uf.union(i, j);
            }
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0;i < n;i++){
            set.add(uf.roots[i]);
            System.out.println(uf.roots[i]);
        }

        return set.size();
    }

    public int findCircleNumBfs(int[][] isConnected){
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int count = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0;i < n;i++){
            if(!visited[i]){
                queue.offer(i);
                while(!queue.isEmpty()){
                    int cur = queue.poll();
                    visited[cur] = true;
                    for(int j = 0;j < n;j++){
                        if(isConnected[cur][j] == 1 && !visited[j]){
                            queue.offer(j);
                        }
                    }
                }
                count++;
            }
        }
        return count;
    }

    public int findCircleNumDfs(int[][] isConnected){
        int n = isConnected.length;
        int count = 0;
        boolean[] visited = new boolean[n];
        for(int i = 0; i < n;i++){
            if(!visited[i]){
                dfs(isConnected, visited, i, n);
                count++;
            }
        }
        return count;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int i, int n){
        for(int j = 0;j < n;j++){
            if(isConnected[i][j] == 1 && !visited[j]){
                visited[j] = true;
                dfs(isConnected, visited, j, n);
            }
        }
    }

    public static void main(String[] args) {
        int[][] isConnected = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        System.out.println(new FindCircleNum().findCircleNum(isConnected));
    }
}
